package backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution90 {

    List<Integer> track = new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        //先排个序，让重复元素堆在一起
        Arrays.sort(nums);
        backTrack(nums,0);
        return result;
    }

    public void backTrack(int[] nums,int start){

        //加入集合
        result.add(new ArrayList<>(track));

        for (int i = start; i < nums.length; i++) {
            //当前num和前一个num重复了，剪枝
            if (i > start && nums[i-1]==nums[i]){
                continue;
            }
            track.add(nums[i]);

            backTrack(nums, i+1);

            track.remove(Integer.valueOf(nums[i]));
        }
    }
}
